package leetcode_101_120;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class minimumTotal_120 {
    /**
     * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
     * 每一步只能移动到下一行中相邻的结点上。
     * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
     * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        /**
         * 关键问题是如果相邻的数字相等的情况
         * 想法是使用一个集合存储该层中所有可以选择的数字下标
         *
         * 写完了发现从上到下不是数字一次·增大，我想当然以为是这种情况
         * 只能重新开始写
         */
        int minimumTotal=triangle.get(0).get(0);
        int index=0;
        List<Integer>sameNum=new ArrayList<>();//存储该层中所有可以选择的数字下标
        sameNum.add(0);
        sameNum.add(1);
        for(int i=1;i<triangle.size()-1;i++){
            int minNum=triangle.get(i).get(sameNum.get(0));  //该层中所有可以选择的数字中最小的数字
            Set<Integer> minSameNum=new HashSet<>();
            //找出最小数字
            for(int t=1;t<sameNum.size();t++){
                if(triangle.get(i).get(sameNum.get(t))<minNum)
                    minNum=triangle.get(i).get(sameNum.get(t));
            }
            //保存可能有多个的最小数字的下标以及右侧的坐标
            for(int t=0;t<sameNum.size();t++){
                if (triangle.get(i).get(sameNum.get(t)) == minNum) {
                    minSameNum.add(sameNum.get(t));
                    if (sameNum.get(t) != i) //防止存入越界下标
                        minSameNum.add(sameNum.get(t) + 1);
                }
            }
            minimumTotal+=minNum;
            //更新下一层中可以选择的位置
            sameNum= new ArrayList<>(minSameNum);
        }
        return minimumTotal;
    }


    public int minimumTotal2(List<List<Integer>> triangle) {
        /**
         * 需要列出所有情况，使用递归比较简单
         * 内存超了
         */
        List<Integer>ans=new ArrayList<>();
        function(triangle,0,0,0,ans);
        int minimumTotal=ans.get(0);
        for(int i=1;i<ans.size();i++){
            if(ans.get(i)<minimumTotal)
                minimumTotal=ans.get(i);
        }
        return minimumTotal;
    }

    /**
     * @param triangle 三角形路径
     * @param minimumTotal 实时路径和
     * @param index 选择的数字下标
     * @param depth 当前递归深度
     * @param ans 结果集
     */
    public void function(List<List<Integer>> triangle,int minimumTotal,int index,int depth,List<Integer>ans) {
        if(depth==triangle.size()-1){ //到达最下一层
            if (index < triangle.get(depth).size() - 1)  //防止越界
                ans.add(minimumTotal + Math.min(triangle.get(depth).get(index), triangle.get(depth).get(index + 1)));
            else
                ans.add(minimumTotal + triangle.get(depth).get(index));
            return;
        }
        function(triangle,minimumTotal+triangle.get(depth).get(index),index,depth+1,ans);
        if (index !=triangle.get(depth).size() - 1)
            function(triangle, minimumTotal + triangle.get(depth).get(index + 1), index + 1, depth + 1, ans);
    }


    /**
     * 高解，在递归中记忆化
     * 解法类似从下往上的动态规划
     * 是从下往上累加的递归,将大小比较在每一层递归都进行，简化步骤
     * 我的写法是从上往下累加还需要考虑越界问题
     * @param triangle
     * @return
     */
    public int minimumTotal3(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return  dfs(triangle, 0, 0);
    }
    Integer[][] memo;
    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        if (memo[i][j] != null) {  //计算过的最小路径就无需再计算，直接返回
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j); //当前元素加下层中最短的路径和
    }

}
